1716D - Chip Move - CodeForces Solution


brute force dp math

Please click on ads to support us..

Python Code:

def solve():
    MOD = 998244353
    n, k = map(int, input().split())
    m, x = 0, 0
    while x <= n:
        x += k+m
        m += 1
    ans = [0]*(n+1)
    dp = [0]*(n+1)
    dp[0] = 1
    x = 0
    for j in range(k, k+m):
        dp1 = [0]*(n+1)
        x += j
        for i in range(x, n+1):
            dp1[i] = (dp1[i]+dp[i-j]+dp1[i-j])%MOD
        dp = dp1
        for i in range(x, n+1):
            ans[i] = (ans[i]+dp[i])%MOD
        
    print(*ans[1:])


import sys
input = lambda: sys.stdin.readline().rstrip()
solve()

C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second 
#define N 200100
const int mod = 998244353;
template<typename T>void print(vector<T>&a,int c=0) {
    for(auto&it :a)cout << it+c<< " ";
    cout << endl;
}
void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
template<typename T>T lcm(T a, T b) {
    return (a * b) / (__gcd(a, b));
}

int main(){
    fast();
    
    /* Code starts here -------------------------------------------> */
    int t = 1;
    // cin>>t;
    while(t--) {
        int n;cin>>n;
        int k;cin>>k;
        vector<int>ans(n + 1, 0), dp1(n + 1, 0);
        dp1[0] = 1;
        for(int mn=0;mn<=n;mn+=(k++)) {
            vector<int>dp2(n + 1, 0);
            for(int i=mn+k;i<=n;i++) {
                dp2[i] = (dp2[i - k] + dp1[i - k]) % mod;
                ans[i] = (ans[i] + dp2[i]) % mod;
            }
            swap(dp1,dp2);
        }
        for(int i=1;i<=n;i++)
            cout << ans[i] << ' ';
        cout << '\n';
    }
    
    
    
    

    
    
    
    
    
    
    

    
    
    
    
    
    return 0;
}


Comments

Submit
0 Comments
More Questions

977C - Less or Equal
1505C - Fibonacci Words
1660A - Vasya and Coins
1660E - Matrix and Shifts
1293B - JOE is on TV
1584A - Mathematical Addition
1660B - Vlad and Candies
1472C - Long Jumps
1293D - Aroma's Search
918A - Eleven
1237A - Balanced Rating Changes
1616A - Integer Diversity
1627B - Not Sitting
1663C - Pōja Verdon
1497A - Meximization
1633B - Minority
688B - Lovely Palindromes
66B - Petya and Countryside
1557B - Moamen and k-subarrays
540A - Combination Lock
1553C - Penalty
1474E - What Is It
1335B - Construct the String
1004B - Sonya and Exhibition
1397A - Juggling Letters
985C - Liebig's Barrels
115A - Party
746B - Decoding
1424G - Years
1663A - Who Tested